package dynamic;

import java.util.*;

import org.junit.Test;

import utils.ArrayGenerator;

public class Ex84 {
    
    //柱狀圖中最大矩形
    public class Solution {

        /* 
            1. 暴力破解：遍历柱子，每次向着两边延伸，达到边界计算最大面积
        */
        public int largestRectangleArea1(int[] heights) {
            int len = heights.length;
            if (len == 0) return 0;
            if (len == 1) return heights[0];

            int res = 0, count, j;
            for (int i = 0; i < len; i++) {
                count = 0;
                j = i - 1;
                while (j >= 0 && heights[j] >= heights[i]) j--;
                count += i - j;
                j = i + 1;
                while (j < len && heights[j] >= heights[i]) j++;
                count += j - i - 1;
                res = Math.max(res, heights[i] * count);
            }
            return res;
        }

        //单调栈法：
        /* 
            我想要知道的是左边和右边第一个大于等于我的下标，其实使用两个栈就可以记录，无需遍历
            
            不行，不能确定较小的元素右边的值
        */
        public int largestRectangleArea2(int[] heights) {
            int len = heights.length;
            if (len == 0) return 0;
            if (len == 1) return heights[0];

            int res = 0;
            Deque<Integer> stack1 = new LinkedList<>();
            Deque<Integer> stack2 = new LinkedList<>();
            //key：元素下标，val：[左边大于我的最近元素， 右边大于我的最近元素]
            Map<Integer, int[]> map = new HashMap<>();

            for (int i = 0; i < len; i++) {
                map.put(i, new int[2]);
                if (stack1.isEmpty() || heights[i] >= heights[stack1.peekLast()]) {
                    stack1.offerLast(i);
                }
            }

            for (int i = len - 1; i >= 0; i--) {
                if (stack2.isEmpty() || heights[i] >= heights[stack2.peekLast()]) {
                    stack2.offerLast(i);
                }
            }

            int idx = 0;
            while (idx < len) {
                while (!stack1.isEmpty() && stack1.peekFirst() <= idx) {
                    stack1.pollFirst();
                }
                map.get(idx++)[0] = stack1.isEmpty() ? -1 : stack1.peekFirst();
            }
            idx = len - 1;
            while (idx >= 0) {
                while (!stack2.isEmpty() && stack2.peekFirst() >= idx) {
                    stack2.pollFirst();
                }
                map.get(idx--)[1] = stack2.isEmpty() ? -1 : stack2.peekFirst();
            }

            map.forEach((k, v) -> System.out.println(Arrays.toString(v)));
            return res;
        }

                //单调栈法：
        /* 
            维护单调递增栈【可以相等】，需要将>cur的元素出栈，并由cur的下标得到出栈元素右边>=他的下标范围。
        */
        public int largestRectangleArea(int[] heights) {
            int len = heights.length;
            if (len == 0) return 0;
            if (len == 1) return heights[0];

            int res = 0, cur;
            Deque<Integer> stack = new LinkedList<>();

            //加左边：不用判断栈空，因为0必定不会出栈
            //加右边：让栈中非0元素全部出栈
            int[] newArray = new int[len + 2];
            System.arraycopy(heights, 0, newArray, 1, len);
            newArray[0] = 0;
            newArray[len + 1] = 0; //最终的单元
            heights = newArray;

            for (int i = 0; i < len + 2; i++) {
                while (!stack.isEmpty() && heights[stack.peekLast()] > heights[i]) {
                    cur = stack.pollLast();
                    int left = stack.peekLast();  //因为在左边加了0，因此肯定比右边所有都小，不会出栈
                    //i,left 为小于cur的元素，其宽度为 i - left - 1
                    res = Math.max((i - left - 1) * heights[cur], res);
                }
                stack.offerLast(i);
            }
            return res;
    }

}
    @Test
    public void test1() {
        Solution s = new Solution();
        int heights[] = {5, 19, 17, 10, 2, 7, 4, 4, 5, 12, 14, 18, 5, 1, 17, 6, 12, 11, 11, 9, 11, 17, 13, 13, 16, 14, 7, 18, 7, 6, 18, 9, 12, 16, 16, 1, 16, 11, 12, 14};
        /* new int[]{2,1,5,6,2,3}; */
        int res = s.largestRectangleArea(heights);
        System.out.println(res);
        System.out.println(Arrays.toString(ArrayGenerator.getArray(20, 40)));
    }

}
